<!DOCTYPE html>
<html>

	<head>
		<meta http-equiv="Content-Type" content="text/html">
		<meta charset="utf-8" />
		<meta http-equiv="X-UA-Compatible" content="IE=edge" />
		<meta name="viewport" content="width=device-width,initial-scale=1,minimum-scale=1,maximum-scale=1,user-scalable=no" />
		<title></title>
	</head>

	<body erke-hide>
	</body>
	<script>
		/**
		 * @param {number} n
		 * @return {number}
		 */
		function fibonacci(n) {
			if(n <= 2) {
				return 1;
			} else {
				if(n % 2 == 0) {
					n = n / 2;
					return fibonacci(n + 1) * fibonacci(n) + fibonacci(n) * (fibonacci(n + 1) - fibonacci(n));
				} else {
					n = (n - 1) / 2;
					return fibonacci(n + 1) * fibonacci(n + 1) + fibonacci(n) * fibonacci(n);
				};
			};
		};

		function fibonacciA(n) {
			var a, b, s;
			if(n <= 2) {
				return 1;
			} else {
				a = 1;
				b = 1;
				for(var i = 3; i <= n; i++) {
					s = a + b;
					a = b;
					b = s;
				};
				return s;
			};
		};
		
		var start,end;
		
		start = Date.now();
		console.log(fibonacci(1000));
		end = Date.now();
		console.log(end-start);
		
		start = Date.now();
		console.log(fibonacciA(1000));
		end = Date.now();
		console.log(end-start);
		
	</script>

</html>